%==========================================================================
%=  This file is part of the Sound Restoration Project
%=  (c) Copyright Industrial Mathematics Institute
%=                University of South Carolina, Department of Mathematics
%=  ALL RIGHTS RESERVED
%=
%=  Author: Borislav Karaivanov
%==========================================================================

%==========================================================================
% List of the files on which this procedure depends:
%
% none
%
%==========================================================================

%==========================================================================
% Below "separated ranges" means ranges such that for any two of them there
% is an integer that does not belong to either of them but is between them.
% For instance, (3:5) and (7:10) are separated because 6 is between them
% but (2:4) and (5:8) are not because there is no integer between 4 and 5.
%==========================================================================
% The function "mergeRangeIntoSeparatedRanges" takes a single range of
% integers and merges it into an existing list of separated ranges of
% integers. The given separated ranges are listed from left to right. The
% same properties are expected for the new list of separated ranges after
% the given range is incorporated - the new ranges should be separated and
% listed from left to right. The function also finds and returns all
% residual subranges of the given single range obtained by excluding the
% integers that belong to any of the existing separated ranges.
% INPUT: "newRange" is a row vector of length two specifying the new
% range of integers.
% "separatedRangesArr" is a 2D array of two columns and many rows. Each row
% represents a range of integers. The ranges are separated (see above) and
% listed in increasing order of their starting points (or ending points for
% that matter).
% OUTPUT: "separatedRangesArr" returns the new collection of separated
% ranges obtained after merging the new range into the existing separated
% ranges. It returns a 2D array of two columns and many rows. Each row
% represents a range of integers. The ranges are separated (see above) and
% listed in increasing order of their starting points (or ending points for
% that matter).
% "residSubRangesArr" returns the collection of residual subranges obtained
% form the given new range by removing the integers belonging to the given
% separated ranges. It returns a 2D array of two columns and many rows.
% Each row represents a range of integers. The residual subranges are
% separated (see above) and listed in increasing order of their starting
% points (or ending points for that matter).
%==========================================================================
function [separatedRangesArr, residSubRangesArr] = ...
    mergeRangeIntoSeparatedRanges(newRange, separatedRangesArr)

% If the given list of separated ranges is empty, then clearly the given
% new range should be used to initialize both outputs.
if (isempty(separatedRangesArr) == true)
    separatedRangesArr = newRange;
    residSubRangesArr = newRange;
    return;
end

% Allocate memory for the residual subranges of the given new range which
% contain integers not belonging to any of the given separated ranges.
residSubRangesArr = zeros(size(separatedRangesArr, 1) + 1, 2);
% Find the index of the first of the separated ranges that is not entirely
% to the left of the given new range.
firstHitInd = find(separatedRangesArr(:, 2) >= newRange(1), 1, 'first');
% Find the index of the last of the separated ranges that is not entirely
% to the right of the given new range.
lastHitInd = find(separatedRangesArr(:, 1) <= newRange(2), 1, 'last');

if (isempty(firstHitInd) == true)
    % All given separated ranges are to the left of the given new range:
    residSubRangesArr = newRange;
    % Update the list of separated ranges keeping it sorted from left to
    % right and making sure that the ranges are separated.
    if (separatedRangesArr(end, 2) == (newRange(1) - 1))
        separatedRangesArr(end, 2) = newRange(2);
    else
        separatedRangesArr = [separatedRangesArr; newRange];
    end
elseif (isempty(lastHitInd) == true)
    % All given separated ranges are to the right of the given new range:
    residSubRangesArr = newRange;
    % Update the list of separated ranges keeping it sorted from left to
    % right and making sure that the ranges are separated.
    if (separatedRangesArr(1, 1) == (newRange(2) + 1))
        separatedRangesArr(1, 1) = newRange(1);
    else
        separatedRangesArr = [newRange; separatedRangesArr];
    end
else
    if (firstHitInd > lastHitInd)
        % The entire given new range is between two separated ranges: the given
        % new range becomes a residual subrange.
        residSubRangesArr = newRange;
    else
        % Some of the given separated ranges meet the given new range:
        currResSubRangeInd = 0;
        % Possibly create a residual subrange at the start of the given new range.
        if (separatedRangesArr(firstHitInd, 1) > newRange(1))
            currResSubRangeInd = currResSubRangeInd + 1;
            residSubRangesArr(currResSubRangeInd, 1) = newRange(1);
            residSubRangesArr(currResSubRangeInd, 2) = separatedRangesArr(firstHitInd, 1) - 1;
        end
        % Create all residual subranges strictly inside the given new range.
        for ind = (firstHitInd + 1):lastHitInd
            currResSubRangeInd = currResSubRangeInd + 1;
            residSubRangesArr(currResSubRangeInd, 1) = separatedRangesArr(ind - 1, 2) + 1;
            residSubRangesArr(currResSubRangeInd, 2) = separatedRangesArr(ind, 1) - 1;
        end
        % Possibly create a residual subrange at the end of the given new range.
        if (separatedRangesArr(lastHitInd, 2) < newRange(2))
            currResSubRangeInd = currResSubRangeInd + 1;
            residSubRangesArr(currResSubRangeInd, 1) = separatedRangesArr(lastHitInd, 2) + 1;
            residSubRangesArr(currResSubRangeInd, 2) = newRange(2);
        end
        % Get rid of any unused entries.
        residSubRangesArr = residSubRangesArr(1:currResSubRangeInd, :);
    end
    
    %======================================================================
    % Note that the new separated ranges are formed in the same way
    % regardless of whether "firstHitInd > lastHitInd" or not.
    %======================================================================
    % Allocate memory for a new separated range possibly combining the
    % given new range with the separated ranges it meets.
    combinedIndRange = zeros(1, 2);
    % If the left end of the given new range touches (but does not meet)
    % one of the given separated ranges, then the two have to be combined.
    if ( (firstHitInd > 1)&&(newRange(1) == (separatedRangesArr(firstHitInd - 1, 2) + 1)) )
        lastLeftOldRangeToKeep = firstHitInd - 2;
        combinedIndRange(1, 1) = separatedRangesArr(firstHitInd - 1, 1);
    else
        lastLeftOldRangeToKeep = firstHitInd - 1;
        combinedIndRange(1, 1) = min(separatedRangesArr(firstHitInd, 1), newRange(1));
    end
    % If the right end of the given new range touches (but does not meet)
    % one of the separated ranges, then the two have to be combined.
    if ( (lastHitInd < size(separatedRangesArr, 1))&&(newRange(2) == (separatedRangesArr(lastHitInd + 1, 1) - 1)) )
        firstRightOldRangeToKeep = lastHitInd + 2;
        combinedIndRange(1, 2) = separatedRangesArr(lastHitInd + 1, 2);
    else
        firstRightOldRangeToKeep = lastHitInd + 1;
        combinedIndRange(1, 2) = max(separatedRangesArr(lastHitInd, 2), newRange(2));
    end
    % Update the list of separated ranges keeping it sorted from left to
    % right and making sure that the ranges are separated.
    separatedRangesArr = [separatedRangesArr(1:lastLeftOldRangeToKeep, :); ...
        combinedIndRange; separatedRangesArr(firstRightOldRangeToKeep:end, :)];
end

return;
% end of the function "mergeRangeIntoSeparatedRanges"
